//
// Created by admin on 2024/7/6.
//
/*二分查找变形
 *查找第一个/ 最后一个值等于给定值的元素  锚定法
 * OJ: https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
 *查找第一个/ 最后一个值大于等于给定值的元素
 *查找最后⼀个⼩于等于 target 的元素，
 * 讲解:
 * https://www.cnblogs.com/sunshuyi/p/12681088.html
 * */

#include <iostream>
#include <vector>

using namespace std;


// 查找第一个等于给定值的元素  用锚定的方法
int searchFirstEqual(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1;
    if (x > v[r] || x < v[l])
        return -1;
    int m;
    int t = -1; // 临时保存等于给定值的下标
    while (l <= r)
    {
        m = (l + r) / 2;
        if (x > v[m])
            l = m + 1;
        else if (x < v[m])
            r = m - 1;
        else
        {
            t = m;
            r = m - 1;
        }
    }
    return t;
}

// 查找第一个值大于等于给定值的元素
// (查找大于等于给定值 最左边的元素)
int searchFirstEqualLarge(vector<int> v, int x)
{
    int l = 0, r = v.size() - 1;
    if (x > v[r])
        return -1;
    int m = (l + r) / 2;
    int t; // 临时保存大于等于给定值的下标
    while (l <= r)
    {
        m = (l + r) / 2;
        if (x <= v[m])
        {
            t = m;  // 找到>=给定值的元素, 先锚定当前下标
            r = m - 1;
        } else
        {
            l = m + 1;
        }
    }
    return t;
}

// 查找最后一个与 target 相等的元素
int searchLastEqualLarge(vector<int> v, int x)
{
    int t = -1, l = 0, r = v.size() - 1;
    while (l <= r)
    {
        int m = r + (l - r) / 2;
        if (x > v[m])
            l = m + 1;
        else if (x < v[m])
            r = m - 1;
        else
        {
            t = m;
            l = m + 1;
        }
    }
    return t;
}

// 查找最后一个小于等于 target 的元素，
int searchLastLessEqual(vector<int> v, int x)
{
    int t = -1, l = 0, r = v.size();
    while(l<=r)
    {
        int m = r+(l-r)/2;
        if(x<v[m])
            r=m-1;
        else
        {
            t=m;
            l=m+1;
        }
    }
    return t;
}

int main()
{
    //                0   1  2  3  4  5  6  7  8  9  10 11 12
    vector<int> l = {-11, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 9, 10};
//    vector<int> l ={1};
//    cout << searchFirstEqual(l,4) << endl;
//    cout<<searchFirstEqualLarge(l,1)<<endl;
//    cout << searchLastEqualLarge(l, 4) << endl;
    cout << searchLastLessEqual(l, 8) << endl;
    return 0;
}